演算法是什麼
演算法是由能夠一步步解決問題的步驟所組成,就像是料理新手學習做一道菜時,通常會跟著食譜一步一步做出來,這時候「食譜」可以說是做出料理的演算法。
假設我今天想學做麻婆豆腐,所以去 Google 麻婆豆腐該怎麼做,結果發現有超多食譜在教人怎麼做出麻婆豆腐,接下來就要開始考量以下問題,選出一份適合我的麻婆豆腐食譜:
- 根據這份食譜,我大概需要花多久時間才能做出來?
- 家裡放得下食譜中需要採買的食材嗎?
- 食譜中需要的食材或廚具會不會很貴?
- 不想出門買菜的話,我能根據這份食譜用家中現有的食材做嗎?
- 如果我照著這份食譜做,有信心做出成功的麻婆豆腐嗎?
好的演算法 vs 不夠好的演算法
如果把一個電腦程式看作演算法,就像食譜一樣,需要考慮類似的問題,而衡量這些問題的評估方式也不同:
- 花的時間 → 時間複雜度
- 佔用的空間 → 空間複雜度
- 正確率 → 實際跑過超多次,看看是否都能成功;或者以理論判斷
- 相容性 → 在 Windows 跟 MacOS 分別跑過,看是否能運作
- 開發成本 → 是不是需要額外學習新的理論或技術
複雜度 Complexity
複雜度的全稱是「漸進複雜度」,主要是從時間與空間的角度來評估演算法的好壞。
- 時間複雜度(Time Complexity):執行時間的長短
- 空間複雜度(Space Complexity):佔用的儲存空間大小
複雜度會受到量級影響,不同時間複雜度/空間複雜度的演算法,在處理大規模資料時,可以看出在時間與空間上的優劣差異。
精確衡量複雜度的方式:大歐跟小歐
說到要比較不同演算法的複雜度,要比較的是當資料量變多時,演算法成長的速度。
假設演算法動一次步驟,花費的時間都是一樣的,這個步驟次數就是 n。因為要模擬處理大規模資料的情境,所以會假想當 n 趨近無窮大來比較複雜度。
極限概念 1
當 n 趨近無窮大,哪個總和會比較大?
- $3n^2 + n + 20$ 與 $100n$
- $n^{100}$ 與 $2^n$
- $n^2$ 與 $10_nlog n$
- $100^n$ 與 $n!$
- $30*2^n$ 與 $3^n$
- $100n$ 與 $200n$
極限的概念 2
上面的比較方式,只單純比較總和結果,但如果只比較總和結果其實不準,就像 A 第一次跟第二次的考試成績分別是 80 跟 100,B 則是 40 跟 50,但 $\frac{80}{40} = \frac{100}{50}$,兩人的進步幅度(成長速度)是相同的,而複雜度要比較的也是成長的速度,為了知道成長的速度差距,就會像前面計算兩人成績的方式一樣,將比較的兩個數相除
- 在 n 趨近無限大時,$\frac{f(n)}{g(n)}$ 的結果趨近於 0,表示 f(n) 的成長速度比 g(n) 小
- 在 n 趨近於無限大時,$\frac{f(n)}{g(n)}$ 的結果也趨近於無限大,表示 f(n) 的成長速度比 g(n) 大
- 否則當兩者是一樣量級,也就是成長速度差不多快
現在問題來了,由於都在假設 n 趨近無限大的情況下比較複雜度量級,每次都要假裝將 n 帶入後心算結果,不論怎麼想都覺得麻煩,所以有了特殊符號,能以簡潔的方式表示複雜度,方便人快速做判斷。這些特殊符號有很多種類,這裡只說明大歐(Big-O)、小歐(Little-o)跟(Big-theta)三種。
大歐(Big-O)
- 通常記為 $O(f(n))$
- $f(n)$ 指的是複雜度量級的上界(最大值),實際執行的結果可能會比用(Big-O)紀錄的數值小。
以下是將演算法改用為大歐符號表示的例子:
演算法算式 | 複雜度符號 |
---|---|
$3n^2 + n + 20$ | $O(n^2)$ |
$100n$ | $O(n)$ |
$n^{100}$ | $O(n^{100})$ |
$2^n$ | $O(2^n)$ |
$n^2$ | $O(n^2)$ |
$10nlog n$ | $O(nlogn)$ |
$100^n$ | $O(100^n)$ |
$n!$ | $O(n!)$ |
$100n$ | $O(n)$ |
$3^n$ | $O(3^n)$ |
$30*2^n$ | $O(2^n)$ |
$200n$ | $O(n)$ |
下圖則表示當資料量變多時,每種大歐需要執行的步驟,例如:$O(1)$ 表示輸入的數值大小與需要執行的步驟無關,執行步驟不受輸入數值影響。
小歐(Little-o)
- 記為 $o(f(n))$
- $f(n)$ 指的是複雜度量級的嚴格上界(絕對的最大值),代表實際執行的數值一定會比轉成 $o(f(n))$ 紀錄的數值小
例如 $3n^3 + 5n^2 + 10n + 3$,以大歐(Big-O)紀錄是 $O(n^3)$,但在小歐(Little-o)要記錄成 $o(n^4)$。兩者的複雜度量級不同。
(Big-theta)
- 記為 $θ(f(n))$
- $f(n)$ 指的是複雜度量級的嚴格上下界,實際執行的數值與(Big-theta)紀錄的數值完全相同。代表不管用哪種複雜度符號紀錄,結果都屬於相同複雜度量級,不會像 $3n^3 + 5n^2 + 10n + 3$,以不同複雜度符號紀錄時,會有不同結果。
這篇文章大致說明了演算法的概念、評估演算法好壞的方式、不同的時間複雜度量級、表示時間複雜度的方式。由於剛接觸演算法,還沒真實體驗到演算法在實務開發的重要性,較難以實際案例比較不同複雜度的演算法。但跟著程式導師計畫的課程進度往下走,下篇內容預計是排序用的演算法,順便了解一個演算法的最理想情況與最壞情況。